Many hardware circuits, such as microprocessors, comprise memory that is accessed by software. In some cases, multiple software threads operate in parallel, either on a single processor or on multiple processors of the hardware circuit. These software threads may access shared memory components. The circuit is usually designed and implemented in accordance with certain synchronization definitions, which specify the order in which different software threads access the memory under different conditions.
Several methods and systems are known in the art for testing the compliance of a design with its memory synchronization definitions. Some methods and systems generate large numbers of random memory access sequences. Such methods are described, for example, by Adir and Shurek in “Generating Concurrent Test-Programs with Collisions for Multi-Processor Verification,” Proceedings of the Seventh IEEE International High-Level Design Validation and Test Workshop (HLDVT'02), Cannes, France, Oct. 27-29, 2002, pages 77-82, and by O'Krafka et al., in “A Portable Test Generator for Cache-Coherent Multiprocessors,” Proceedings of the 1995 IEEE Fourteenth Annual International Phoenix Conference on Computers and Communications, Scottsdale, Ariz., Mar. 28-31, 1995, pages 38-44.
Methods and systems based on random test generation are often accompanied by monitoring methods and systems for detecting synchronization violations. Such methods and systems are described, for example, by Raghavan et al., in “Multiprocessor System Verification through Behavioral Modeling and Simulation,” Proceedings of the 1995 IEEE Fourteenth Annual International Phoenix Conference on Computers and Communications, Scottsdale, Ariz., Mar. 28-31, 1995, pages 396-402, and by Saha et al., in “A Simulation-Based Approach to Architectural Verification of Multiprocessor Systems,” Proceedings of the 1995 IEEE Fourteenth Annual International Phoenix Conference on Computers and Communications, Scottsdale, Ariz., Mar. 28-31, 1995, pages 34-37.
Other synchronization compliance testing methods generate tests aimed at detecting specific synchronization events. Such methods are described, for example, by Adir et al., in “Information-Flow Models for Shared Memory with an Application to the PowerPC Architecture,” IEEE Transactions on Parallel and Distributed Systems, May, 2003, pages 502-515. Other methods that target specific synchronization violation scenarios are described by Collier in “Reasoning about Parallel Architectures,” Prentice Hall, February, 1992, chapter 1, pages 1-13.